1807F - Bouncy Ball - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#define int         long long
#define sz(x)       ((int) (x).size())
#define all(x)      (x).begin(), (x).end()
#define pii         pair<int, int>
#define vi          vector<int>
#define vpii        vector<pii>
#define ff          first
#define ss          second
#define pb          push_back



int dfs(vector<vector<vector<vi>>> &grid, int n, int m, int x, int y, int xDir, int yDir, int tX, int tY) {

    // cout << x << " " << y << " " << xDir << " " << yDir << endl;

    grid[x][y][xDir][yDir] = 1;

    int x1 = x + ((xDir) ? 1 : -1);
    int y1 = y + ((yDir) ? 1 : -1);

    if(x1 == tX && y1 == tY) {
        return 0;
    }
    
    int f = 0;

    if(x1 == 0 || x1 == n + 1)
        xDir = 1 - xDir, f = 1;
    
    if(y1 == 0 || y1 == m + 1)
        yDir = 1 - yDir, f = 1;

    if(f == 1) {

        if(grid[x][y][xDir][yDir] == 1)
            return -1;
        
        int res = dfs(grid, n, m, x, y, xDir, yDir, tX, tY);

        return ((res == -1) ? -1 : (1 + res));
    }

    x1 = x + ((xDir) ? 1 : -1);
    y1 = y + ((yDir) ? 1 : -1);

    if(grid[x1][y1][xDir][yDir] == 1) {
        return -1;
    }

    int res = dfs(grid, n, m, x1, y1, xDir, yDir, tX, tY);

    return (res == -1) ? -1 : res;

}

void solve() {
    int n, m, x1, y1, x2, y2;
    string s;
    cin >> n >> m >> x1 >> y1 >> x2 >> y2 >> s;

    if(x1 == x2 && y1 == y2) {
        cout << 0 << "\n";
        return;
    }
 
    vector<vector<vector<vi>>> grid(n + 1, vector<vector<vi>>(m + 1, vector<vi>(2, vi(2, 0))));

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            grid[i][j][0][0] = 0;
            grid[i][j][0][1] = 0;
            grid[i][j][1][0] = 0;
            grid[i][j][1][1] = 0;
        }
    }

    int res = 0;

    int xDir = 1, yDir = 1;

    if(s[0] == 'U')
        xDir = 0;
    if(s[1] == 'L')
        yDir = 0;

    res = dfs(grid, n, m, x1, y1, xDir, yDir, x2, y2);

    cout << res << endl;

}
 
int32_t main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    
    int tt = 1;
    cin >> tt;
    while (tt--) solve();

    return 0;
}